import React from 'react'
import ReactDOM from 'react-dom'
import { useEffect } from "react"

const App = () => {

useEffect(() => {
  init2()
}, [])

// 放弃思考
const init1 = () => {
  const n = 4, k = 2
  let result = []
  for(let i = 1; i <= n; i++) {
    for(let j = 2; j <= n; j++) {
      let info = [i, j]
      if(i < j) {
        result.push(info)
      }
    }
  }
  console.log(result)
}

// 普通递归
const init2 = () => {
  const n = 4, k = 2
  let result = [], item = []
  const backTrace = () => {
    if(item.length === k) {
      result.push([...item])
      return 
    }
    for(let i = 1; i <= n; i++) {
      item.push(i)
      backTrace(item)
      item.pop()
    }
  }
  backTrace()
  console.log(result)
}

// 递归+降低时间复杂度
const init3 = () => {
  const n = 4, k = 2
  let result = [], item = []
  const backTrace = (startIndex) => {
    if(item.length === k) {
      result.push([...item])
      return 
    }
    for(let i = startIndex; i <= n; i++) {
      item.push(i)
      backTrace(i + 1)
      item.pop()
    }
  }
  backTrace(1)
  console.log(result)
}

// 递归+过滤重复+剪枝
const init4 = () => {
  const n = 4, k = 2
  let result = [], item = []
  const backTrace = (startIndex) => {
    if(item.length === k) {
      result.push([...item])
      return 
    }
    for(let i = startIndex; i <= n - (k - item.length) + 1; i++) {
      item.push(i)
      backTrace(i + 1)
      item.pop()
    }
  }
  backTrace(1)
  console.log(result)
}

  return (
    <>看右边</>
  )
}

export default ReactDOM.render(<App />, document.querySelector('#root'))
